package 剑指Offer.medium;

public class 剪绳子 {
    class Solution {
        public int cuttingRope(int n) {
            int[] dp = new int[n + 1];
            dp[2] = 1;//初始化
            for (int i = 3; i < n + 1; i++) {
                //对某一确定长度的绳子，找到两分的最大值；每段都两分，宏观上就是m分
                for (int j = 2; j < i; j++) {
                    //找到当前规划最大值，与曾经规划做比较
                    int temp = Math.max(j * (i - j), j * dp[i - j]);
                    dp[i] = temp > dp[i] ? temp : dp[i];
                }
            }
            return dp[n];
        }
    }
}
